package test.n00500;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

import static utils.Tools.listOf;

public class Problem00561 {
    public static void main(String[] args) {
        println(new int[][]{
                {1, 3}, {2, 6}, {8, 10}, {15, 18}
        });
        println(new int[][]{
                {1, 4}, {4, 5}
        });
        println(new int[][]{
                {1, 4}, {0, 4}
        });
        println(new int[][]{
                {2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}
        });
    }

    public static void println(int[][] matrix) {
        Solution ss = new Solution();
        System.out.println(listOf(matrix) + "," + ss.merge(matrix));
    }

    public static class Solution {

        /**
         * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/merge-intervals
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         * @param intervals
         * @return
         */
        public int[][] merge(int[][] intervals) {
            List<int[]> result = new ArrayList<>();

            if (intervals.length <= 1) {
                return intervals;
            }
            Arrays.sort(intervals, Comparator.comparingInt(array -> array[0]));
            result.add(intervals[0]);

            for (int i = 1; i < intervals.length; i++) {
                if (result.get(result.size() - 1)[1] >= intervals[i][0]) {
                    result.get(result.size() - 1)[1] = Math.max(intervals[i][1], result.get(result.size() - 1)[1]);
                } else {
                    result.add(intervals[i]);
                }
            }
            return result.toArray(new int[0][]);
        }
    }
}
